가능성의 기하학
볼록 문제에서 등식 제약 조건 $Ax=b$를 가질 경우, 벡터 $v \in \mathbf{R}^n$는 가능한 방향 $Av = 0$인 경우입니다. 즉, 방향 $v$로 움직였을 때 제약 조건이 유지됨을 의미합니다: $Ax=b$이면 $A(x+v)=b$입니다.
$x^*$가 최적이 되려면, 영공간 $\mathcal{N}(A)$ 내의 모든 가능한 방향 $v$에 대해 방향 도함수 $\nabla f(x^*)^T v$가 0이어야 합니다. 이는 그라디언트 $\nabla f(x^*)$가 $\mathcal{N}(A)$와 직교해야 함을 의미하며, 이를 통해 라그랑주 승수의 존재로 이어집니다.
점 $x^*$가 최적이 되려면, 유일하게 벡터 $\nu^* \in \mathbb{R}^p$가 존재하여 다음 조건을 만족해야 합니다:
$\nabla f(x^*) + A^T \nu^* = 0$
이 식은 목적 함수의 감소와 제약 조건의 매니폴드 사이의 평형 상태를 특징짓는 선형 방정식계를 형성합니다.
투영된 그라디언트
그 유클리드 투영 $-\nabla f(x)$의 음의 그라디언트를 영공간 $\mathcal{N}(A)$ 위로 투영한 값은 다음과 같습니다:
$\Delta x_{\text{pg}} = \text{argmin}_{Au=0} \| -\nabla f(x) - u \|_2$
이 벡터는 '최선의' 가능 내림 방향을 나타냅니다. 중요한 점은, $x$가 최적이 될 때만 $\Delta x_{\text{pg}} = 0$이 됩니다.
KKT 시스템과 행렬 성질
블록 시스템을 사용하면 뉴턴 단계와 이중 변수를 동시에 해석할 수 있습니다:
$$\begin{bmatrix} I & A^T \\ A & 0 \end{bmatrix} \begin{bmatrix} v \\ w \end{bmatrix} = \begin{bmatrix} -\nabla f(x) \\ 0 \end{bmatrix}$$행렬 스펙트럼 성질에 대한 참고: KKT 행렬은 대칭이지만 부정의입니다. 만약 행렬이 비특이적이라면, 정확히 $n$개의 양수와 $p$개의 음수 고유값을 가집니다. 이는 최적점 $(x^*, \nu^*)$가 안장점 라그랑주 함수 $L(x, \nu) = f(x) + \nu^T(Ax-b)$의 안장점이며, 결합된 원시-쌍대 공간에서 단순한 국부 최솟값이 아님을 의미합니다.